# Closest Pair

• 2026년 7월 2일 알고리즘
  추가 설명 — 균형 이진 탐색 트리는 어떻게 y로 정렬하고 구간을 찾는가

  가장 가까운 점 쌍 ③에서 활성 집합을 떠받친 균형 BST(std::set)의 내부를 본다. 왜 정렬 배열·연결 리스트가 아닌 균형 BST인지, y를 키로 두면 왜 트리가 곧 y정렬인지, [y-D, y+D] 구간을 O(log n + 개수)에 찾는 원리를 짚는다.

• 2026년 7월 2일 알고리즘
  가장 가까운 점 쌍 ③ — Plane Sweeping과 균형 이진 탐색 트리

  2편과 같은 O(n log n)에 다른 시선으로 닿는다. 점을 x좌표 순으로 훑으며 폭 D 안의 점만 균형 BST(std::set)에 담는 Plane Sweeping으로, y좌표 [y-D, y+D] 구간만 조회한다. 후보가 상수 개임을 보여 전체 O(n log n)을 유도한다.

• 2026년 7월 1일 알고리즘
  가장 가까운 점 쌍 ② — 정렬을 유지해 O(n log n)으로

  1편 O(n log²n)의 여분 log n은 combine마다 y정렬을 다시 하는 데서 나온다. 재귀가 y로 정렬된 결과를 반환하게 만들어 combine을 O(n) merge로 바꾸고, 분할은 x·순서는 y로 유지해 전체를 O(n log n)으로 끌어내린다.

• 2026년 6월 30일 알고리즘
  추가 설명 — 왜 다음 7개만 비교하면 되는가

  가장 가까운 점 쌍의 combine에서, 한 점이 옆에 있는 점을 몇 개만 비교해도 되는 이유를 쉽게 풀어 본다. 핵심은 '가까운 점은 좁은 공간에 빽빽이 들어갈 수 없다'는 것. 후보가 들어올 칸을 잘게 쪼개 세면, 비교 대상이 n과 무관한 상수(최대 7개)로 묶인다.

• 2026년 6월 30일 알고리즘
  가장 가까운 점 쌍 ① — 분할 정복과 O(n log²n)

  2차원 평면에서 가장 가까운 두 점을 찾는 문제. 모든 쌍을 보면 O(n²)이지만, 분할 정복으로 더 빠르게 풀 수 있다. x좌표로 좌우를 나눠 각 영역의 최소 거리 D를 구한 뒤, 경계의 폭 D 밴드만 합치는 과정을 보고 O(n log²n)임을 유도한다.